package com.zhn;

/**
 * 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
 *
 * 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
 */

import java.util.Stack;

public class SearchBST {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null || root.val == val){
            return root;
        }
        Stack<TreeNode> stack = new Stack<>();
//        和stack.push(root);效果一样，可以替换
        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode pop = stack.pop();
            if(val == pop.val){
                return pop;
            }
            if(pop.right != null)stack.push(pop.right);
            if(pop.left != null) stack.push(pop.left);
        }
        return null;
    }
}
